The present invention relates to determining the period of signals encoded by a pseudo-random binary sequence, and sampled analog signals obtained after line coding a pseudo-random binary sequence.
Pseudo-random binary sequences are frequently used in digital communications systems, for example in magnetic recording systems. Usually, such sequences are generated using linear feedback registers to ensure periodicity. The structure of the binary data generator is given by the characteristic polynomial describing the pseudo-random binary sequence. The orders of the characteristic polynomials typically span a range of from 3 to 30 and even higher.
In a digital communication system, a stream of data bits, generated by the linear feedback register, represents a data signal having a period TPER. The resulting signal is periodic, with the number of bits in one period determined by the characteristic polynomial of the pseudo-random binary sequence. Usually, sequences are used which have the property that one pattern has the maximum possible length (number of bits) for the order of the characteristic polynomial, termed pseudo-noise (PN) sequences. For example, for a PN sequence with a characteristic polynomial of order N the number of bits in the resulting bit pattern is L=2Nxe2x88x921. In the following description, the repeat cycle time of the bit pattern is intended to be the period of the pseudo-random binary sequence.
Determining the period of PN sequence generated signals is necessary for many applications in digital communications. The procedure usually requires the comparison of the signal being analyzed with a delayed version of itself. For speed, a time-windowed part of the signal is used. In prior art methods, the window was required to contain at least one full period of L bits of the signal for the known algorithms to successfully determine the period of the PN sequence.
The present invention proposes a methodology for detecting the signal period which takes maximum advantage of the fact that the signal is generated based on a pseudo-random binary sequence, and of the fact that the order of the characteristic polynomial is known.
L is the number of bits per pattern generated by a characteristic polynomial of order N; in particular, for a PN sequence L=2Nxe2x88x921 (as described above). The inventor realized that the order N of the characteristic polynomial is the minimum number of successive bits in the pattern which are non-repeating in any sub-sequence of L consecutive bits containing all the N previously mentioned bits. Thus, known algorithms may be used successfully to detect the data signal period, using a time-windowed part of the signal containing as few as N bits. This N bit long subsequence functions as a waveform xe2x80x98tokenxe2x80x99, which is included in the signal, and repeats with exactly the same period as the signal itself.
In known systems, using known period detection algorithms, the length of the token is usually taken to be L=2Nxe2x88x921 bits. Because the time required by a given algorithm to determine the period increases linearly with the bit width of the token used (i.e. scales linearly), a system according to the present invention would give a speed improvement of                               Δ          ⁢                      xe2x80x83                    ⁢          S                =                                            2              N                        -            1                    N                                    (        1        )            
L/N over the prior art systems. Specifically, in the case of PN sequences, widely used as pseudo-random sequences, the speed improvement xcex94S is given in equation (1). For N=7 (i.e. L=127) the speed improvement is 18; for N=9 it is 56, and increases almost 2 times for each integral increase in the order N of the characteristic polynomial.
A system for determining the period of a data signal encoded using PN sequences may be implemented using software, analyzing encoded bit stream signals which have been sampled and stored in a memory. When implemented in this form, a system according to the present invention is highly portable. For example, it may be implemented in software code developed using a high-level programming language (e.g. JAVA). It differs from known art (described above) because it is uses knowledge about the structure of the signal generator (i.e. the order of the characterizing polynomial of the encoding PN sequence), and recognizes the fact that short data tokens from the original signal can be used with the same success in determining the period as longer sequences having at least the length of the period. Such code does not require any specific period detecting algorithm for the its core period detection mechanism. Instead, it works as a pre-filter reducing the amount of data which must be processed by the detection algorithm. Another advantage of systems according to the present invention is that they may be implemented on systems that lack a powerful general purpose processor, for example, digitizing oscilloscopes. The increase of processing speed made possible by the present invention would make feasible a number of data processing applications for the digital communications market in such systems.